package Math;

public class _400_NthDigit {
    //solution 1:overflow,counts every bits's value and use n to sub them to get the
    //bits, then get the number and the single number
    public int findNthDigit_0(int n) {
        double[] counts = new double[32];
        int prev = 10, bits = 1;
        counts[0] = 9;
        for (int i = 1; i < 32; i++) {
            bits += 1;
            int temp = prev * 10;
            counts[i] = (temp - prev) * bits + counts[i - 1];
            System.out.println(counts[i]);
            prev = temp;
        }
        int pos = 0;
        for (int i = 0; i < counts.length - 1; i++) {
            if (counts[i] < n && n <= counts[i + 1]) {
                pos = i;
                break;
            }
        }
        //get the interval's begin number
        int begin = 1;
        for (int i = 0; i < pos; i++) {
            begin *= 10;
        }
        //sub the counts[i-1]'s value;
        double interval = n - counts[pos];
        double number = 0;
        //get the number
        if (interval % (pos + 1) != 0) {
            number = interval / (pos + 1);
            number = begin + number;
            String temp = number + "";
            return Integer.parseInt(temp.charAt(temp.length() - 1) + "");
        } else {
            number = interval / (pos + 1) + 1;
            String temp = number + "";
            return Integer.parseInt(temp.charAt((int) (interval % (pos + 1))) + "");
        }
    }

    //reference solution:sub every loop to minimize the calculation
    public int findNthDigit(int n) {
        int len = 1;
        int start = 1;
        long count = 9;
        while (n > len *count) {
            n -= len * count;
            len++;
            count *= 10;
            start *= 10;
        }
        start += (n - 1) / len;
        String number = Integer.toString(start);
        return Character.getNumericValue(number.charAt((n - 1) % len));
    }
}